Binary search for an ORDERED list (only)ΒΆ
Write a python program for Binary Search for an ORDERED list.
Test Data :
ordered_binary_search([0, 1, 3, 8, 14, 18, 19, 34, 52], 3) -> True
ordered_binary_search([0, 1, 3, 8, 14, 18, 19, 34, 52], 17) -> False
def ordered_binary_search(OA, N):
if len(OA) == 0:
return False
else:
mid = len(OA) // 2
if OA[mid] == N:
return True
else:
if N < OA[mid]:
return binary_search(OA[:mid], N)
else:
return binary_search(OA[mid+1:], N)
def binary_search(A, N):
first = 0
last = len(A) - 1
found = False
while first <= last and not found:
mid = (first + last) // 2
if A[mid] == N:
found = True
else:
if N < A[mid]:
last = mid - 1
else:
first = mid + 1
return found
print(ordered_binary_search([0, 1, 3, 8, 14, 18, 19, 34, 52], 3)) # True
print(ordered_binary_search([0, 1, 3, 8, 14, 18, 19, 34, 52], 17)) # False